package com.sukaiyi.leetcode._55jump_game;

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

/**
 * 跳跃游戏
 * <p>
 * 给定一个非负整数数组，你最初位于数组的第一个位置。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 判断你是否能够到达最后一个位置。
 *
 * @author sukaiyi
 * @date 2020/04/17
 * @see <a href="https://leetcode-cn.com/problems/jump-game//">题目地址</a>
 */
public class Solution {

    @Test
    public void test() {
        assertTrue(canJump(new int[]{3, 2, 1}));
        assertTrue(canJump(new int[]{2, 3, 1, 1, 4}));
        assertFalse(canJump(new int[]{3, 2, 1, 0, 4}));
    }

    public boolean canJump(int[] nums) {
        return canJump(0, nums, new int[nums.length]);
    }

    /**
     * 以指定起点跳，是否能跳到最后一个元素
     *
     * @param start 起点
     * @param nums  跳跃数组
     * @param table 打表节约时间 0: 未执行， -1 false, 1 true
     * @return 是否能到达最后一个元素
     */
    public boolean canJump(int start, int[] nums, int[] table) {
        if (nums.length - start <= 1) { // 已经在最后一个位置
            return true;
        } else if (nums.length - start <= 2) { //在倒数第二个位置
            return nums[nums.length - 2] != 0;
        } else { // 在更前面
            //当前位置可以跳几步
            int step = nums[start];
            // 从 step - 1 步，依次尝试
            for (int i = step; i >= 1; i--) {
                int to = start + i;
                if (to >= nums.length) { // 跳出了范围
                    continue;
                }
                int result = table[to];
                if (result == 0) {
                    boolean can = canJump(to, nums, table);
                    table[to] = can ? 1 : -1;
                }
                if (table[to] == 1) {
                    return true;
                }
            }
            return false;
        }
    }


}
